class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result=[]
        now=[root]
        childs=[]
        direction=True
        while now:
            if direction:
                result.append([i.val for i in now])
            else:
                result.append([i.val for i in reversed(now)])
            while now:
                node=now.pop(0)
                if node.left:
                    childs.append(node.left)
                if node.right:
                    childs.append(node.right)
            now=childs
            childs=[]
            direction=not direction
        return result
    '''
    执行用时：
44 ms
, 在所有 Python3 提交中击败了
56.50%
的用户
内存消耗：
13.8 MB
, 在所有 Python3 提交中击败了
18.12%
的用户
    '''

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result=[]
        now=[root]
        childs=[]
        direction=True
        while now:
            vals=[]
            while now:
                node=now.pop()
                vals.append(node.val)
                if direction:
                    if node.left:
                        childs.append(node.left)
                    if node.right:
                        childs.append(node.right)
                else:
                    if node.right:
                        childs.append(node.right)  
                    if node.left:
                        childs.append(node.left)                  
            now=childs
            childs=[]
            result.append(vals)
            direction=not direction

        return result

'''
执行用时：
32 ms
, 在所有 Python3 提交中击败了
98.08%
的用户
内存消耗：
13.7 MB
, 在所有 Python3 提交中击败了
49.61%
的用户
'''